/**
 * https://leetcode-cn.com/problems/find-the-duplicate-number/
 * 寻找重复数
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
 *假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
 *你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
 * @param nums
 */
const findDuplicate = (nums: number[]) => {
  const len = nums.length;
  let s = 0,
    e = len,
    ans = -1;
  while (s < e) {
    let mid = (s + e) >> 1;
    let cnt = 0;

    // 统计小于等于中间索引的个数
    for (let i = 0; i < len; i++) {
      cnt += +(nums[i] <= mid);
    }

    if (cnt <= mid) {
      // 小于等于中间元素, 往后找
      s = mid + 1;
    } else {
      // 往前找, 前面可能是真正的答案并且ans就是mid
      e = mid;
      ans = mid;
    }
  }
  // 返回答案
  return ans;
};

const findDuplicate2 = (nums: number[]): number => {
  const len = nums.length;

  for (let i = 0; i < len; i++) {
    const cur = nums[i];
    // 如果该值所在的位置不等于当前位置并且将要移动到的位置的值和当前的值一样, 那么这个值就是重复的
    if (cur - 1 !== i && nums[cur - 1] === cur) return cur;

    // 如果不一样, 一直交换
    while (nums[nums[i] - 1] !== nums[i]) {
      const tmp = nums[nums[i] - 1];
      nums[nums[i] - 1] = nums[i];
      nums[i] = tmp;
    }
  }
  // 最后都没有匹配到, 返回最后一个
  return nums[len - 1];
};

// console.log(findDuplicate([1, 3, 4, 2, 2]));
console.log(findDuplicate([3, 1, 3, 4, 2]));
